<html>
  <head>
  <title>eightpuzzle.py</title>
  </head>
  <body>
  <h3>eightpuzzle.py (<a href="../eightpuzzle.py">original</a>)</h3>
  <hr>
  <pre>
<span style="color: green; font-style: italic"># eightpuzzle.py
# --------------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

</span><span style="color: blue; font-weight: bold">import </span>search
<span style="color: blue; font-weight: bold">import </span>random

<span style="color: green; font-style: italic"># Module Classes

</span><span style="color: blue; font-weight: bold">class </span>EightPuzzleState<span style="font-weight: bold">:
 </span><span style="color: darkred">"""
 The Eight Puzzle is described in the course textbook on
 page 64.

 This class defines the mechanics of the puzzle itself.  The
 task of recasting this puzzle as a search problem is left to
 the EightPuzzleSearchProblem class.
 """

 </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>numbers <span style="font-weight: bold">):
   </span><span style="color: darkred">"""
     Constructs a new eight puzzle from an ordering of numbers.

   numbers: a list of integers from 0 to 8 representing an
     instance of the eight puzzle.  0 represents the blank
     space.  Thus, the list

       [1, 0, 2, 3, 4, 5, 6, 7, 8]

     represents the eight puzzle:
       -------------
       | 1 |   | 2 |
       -------------
       | 3 | 4 | 5 |
       -------------
       | 6 | 7 | 8 |
       ------------

   The configuration of the puzzle is stored in a 2-dimensional
   list (a list of lists) 'cells'.
   """
   </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells <span style="font-weight: bold">= []
   </span>numbers <span style="font-weight: bold">= </span>numbers<span style="font-weight: bold">[:] </span><span style="color: green; font-style: italic"># Make a copy so as not to cause side-effects.
   </span>numbers<span style="font-weight: bold">.</span>reverse<span style="font-weight: bold">()
   </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">( </span><span style="color: red">3 </span><span style="font-weight: bold">):
     </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">.</span>append<span style="font-weight: bold">( [] )
     </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">( </span><span style="color: red">3 </span><span style="font-weight: bold">):
       </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>row<span style="font-weight: bold">].</span>append<span style="font-weight: bold">( </span>numbers<span style="font-weight: bold">.</span>pop<span style="font-weight: bold">() )
       </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] == </span><span style="color: red">0</span><span style="font-weight: bold">:
         </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>blankLocation <span style="font-weight: bold">= </span>row<span style="font-weight: bold">, </span>col

 <span style="color: blue; font-weight: bold">def </span>isGoal<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
   </span><span style="color: darkred">"""
     Checks to see if the puzzle is in its goal state.

       -------------
       |   | 1 | 2 |
       -------------
       | 3 | 4 | 5 |
       -------------
       | 6 | 7 | 8 |
       -------------

   &gt;&gt;&gt; EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).isGoal()
   True

   &gt;&gt;&gt; EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).isGoal()
   False
   """
   </span>current <span style="font-weight: bold">= </span><span style="color: red">0
   </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">( </span><span style="color: red">3 </span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">( </span><span style="color: red">3 </span><span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">if </span>current <span style="font-weight: bold">!= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">]:
        </span><span style="color: blue; font-weight: bold">return False
      </span>current <span style="font-weight: bold">+= </span><span style="color: red">1
   </span><span style="color: blue; font-weight: bold">return True

 def </span>legalMoves<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
   </span><span style="color: darkred">"""
     Returns a list of legal moves from the current state.

   Moves consist of moving the blank space up, down, left or right.
   These are encoded as 'up', 'down', 'left' and 'right' respectively.

   &gt;&gt;&gt; EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).legalMoves()
   ['down', 'right']
   """
   </span>moves <span style="font-weight: bold">= []
   </span>row<span style="font-weight: bold">, </span>col <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>blankLocation
   <span style="color: blue; font-weight: bold">if</span><span style="font-weight: bold">(</span>row <span style="font-weight: bold">!= </span><span style="color: red">0</span><span style="font-weight: bold">):
     </span>moves<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span><span style="color: red">'up'</span><span style="font-weight: bold">)
   </span><span style="color: blue; font-weight: bold">if</span><span style="font-weight: bold">(</span>row <span style="font-weight: bold">!= </span><span style="color: red">2</span><span style="font-weight: bold">):
     </span>moves<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span><span style="color: red">'down'</span><span style="font-weight: bold">)
   </span><span style="color: blue; font-weight: bold">if</span><span style="font-weight: bold">(</span>col <span style="font-weight: bold">!= </span><span style="color: red">0</span><span style="font-weight: bold">):
     </span>moves<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span><span style="color: red">'left'</span><span style="font-weight: bold">)
   </span><span style="color: blue; font-weight: bold">if</span><span style="font-weight: bold">(</span>col <span style="font-weight: bold">!= </span><span style="color: red">2</span><span style="font-weight: bold">):
     </span>moves<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span><span style="color: red">'right'</span><span style="font-weight: bold">)
   </span><span style="color: blue; font-weight: bold">return </span>moves

 <span style="color: blue; font-weight: bold">def </span>result<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>move<span style="font-weight: bold">):
   </span><span style="color: darkred">"""
     Returns a new eightPuzzle with the current state and blankLocation
   updated based on the provided move.

   The move should be a string drawn from a list returned by legalMoves.
   Illegal moves will raise an exception, which may be an array bounds
   exception.

   NOTE: This function *does not* change the current object.  Instead,
   it returns a new object.
   """
   </span>row<span style="font-weight: bold">, </span>col <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>blankLocation
   <span style="color: blue; font-weight: bold">if</span><span style="font-weight: bold">(</span>move <span style="font-weight: bold">== </span><span style="color: red">'up'</span><span style="font-weight: bold">):
     </span>newrow <span style="font-weight: bold">= </span>row <span style="font-weight: bold">- </span><span style="color: red">1
     </span>newcol <span style="font-weight: bold">= </span>col
   <span style="color: blue; font-weight: bold">elif</span><span style="font-weight: bold">(</span>move <span style="font-weight: bold">== </span><span style="color: red">'down'</span><span style="font-weight: bold">):
     </span>newrow <span style="font-weight: bold">= </span>row <span style="font-weight: bold">+ </span><span style="color: red">1
     </span>newcol <span style="font-weight: bold">= </span>col
   <span style="color: blue; font-weight: bold">elif</span><span style="font-weight: bold">(</span>move <span style="font-weight: bold">== </span><span style="color: red">'left'</span><span style="font-weight: bold">):
     </span>newrow <span style="font-weight: bold">= </span>row
     newcol <span style="font-weight: bold">= </span>col <span style="font-weight: bold">- </span><span style="color: red">1
   </span><span style="color: blue; font-weight: bold">elif</span><span style="font-weight: bold">(</span>move <span style="font-weight: bold">== </span><span style="color: red">'right'</span><span style="font-weight: bold">):
     </span>newrow <span style="font-weight: bold">= </span>row
     newcol <span style="font-weight: bold">= </span>col <span style="font-weight: bold">+ </span><span style="color: red">1
   </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
     </span><span style="color: blue; font-weight: bold">raise </span><span style="color: red">"Illegal Move"

   </span><span style="color: green; font-style: italic"># Create a copy of the current eightPuzzle
   </span>newPuzzle <span style="font-weight: bold">= </span>EightPuzzleState<span style="font-weight: bold">([</span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">])
   </span>newPuzzle<span style="font-weight: bold">.</span>cells <span style="font-weight: bold">= [</span>values<span style="font-weight: bold">[:] </span><span style="color: blue; font-weight: bold">for </span>values <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">]
   </span><span style="color: green; font-style: italic"># And update it to reflect the move
   </span>newPuzzle<span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] = </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>newrow<span style="font-weight: bold">][</span>newcol<span style="font-weight: bold">]
   </span>newPuzzle<span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>newrow<span style="font-weight: bold">][</span>newcol<span style="font-weight: bold">] = </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">]
   </span>newPuzzle<span style="font-weight: bold">.</span>blankLocation <span style="font-weight: bold">= </span>newrow<span style="font-weight: bold">, </span>newcol

   <span style="color: blue; font-weight: bold">return </span>newPuzzle

 <span style="color: green; font-style: italic"># Utilities for comparison and display
 </span><span style="color: blue; font-weight: bold">def </span>__eq__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>other<span style="font-weight: bold">):
   </span><span style="color: darkred">"""
       Overloads '==' such that two eightPuzzles with the same configuration
     are equal.

     &gt;&gt;&gt; EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]) == \
         EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).result('left')
     True
   """
   </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">( </span><span style="color: red">3 </span><span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>row<span style="font-weight: bold">] != </span>other<span style="font-weight: bold">.</span>cells<span style="font-weight: bold">[</span>row<span style="font-weight: bold">]:
        </span><span style="color: blue; font-weight: bold">return False
   return True

 def </span>__hash__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
   </span><span style="color: blue; font-weight: bold">return </span>hash<span style="font-weight: bold">(</span>str<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">))

 </span><span style="color: blue; font-weight: bold">def </span>__getAsciiString<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
   </span><span style="color: darkred">"""
     Returns a display string for the maze
   """
   </span>lines <span style="font-weight: bold">= []
   </span>horizontalLine <span style="font-weight: bold">= (</span><span style="color: red">'-' </span><span style="font-weight: bold">* (</span><span style="color: red">13</span><span style="font-weight: bold">))
   </span>lines<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>horizontalLine<span style="font-weight: bold">)
   </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>cells<span style="font-weight: bold">:
     </span>rowLine <span style="font-weight: bold">= </span><span style="color: red">'|'
     </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>row<span style="font-weight: bold">:
       </span><span style="color: blue; font-weight: bold">if </span>col <span style="font-weight: bold">== </span><span style="color: red">0</span><span style="font-weight: bold">:
         </span>col <span style="font-weight: bold">= </span><span style="color: red">' '
       </span>rowLine <span style="font-weight: bold">= </span>rowLine <span style="font-weight: bold">+ </span><span style="color: red">' ' </span><span style="font-weight: bold">+ </span>col<span style="font-weight: bold">.</span>__str__<span style="font-weight: bold">() + </span><span style="color: red">' |'
     </span>lines<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>rowLine<span style="font-weight: bold">)
     </span>lines<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>horizontalLine<span style="font-weight: bold">)
   </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'\n'</span><span style="font-weight: bold">.</span>join<span style="font-weight: bold">(</span>lines<span style="font-weight: bold">)

 </span><span style="color: blue; font-weight: bold">def </span>__str__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
   </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>__getAsciiString<span style="font-weight: bold">()

</span><span style="color: green; font-style: italic"># TODO: Implement The methods in this class

</span><span style="color: blue; font-weight: bold">class </span>EightPuzzleSearchProblem<span style="font-weight: bold">(</span>search<span style="font-weight: bold">.</span>SearchProblem<span style="font-weight: bold">):
  </span><span style="color: darkred">"""
    Implementation of a SearchProblem for the  Eight Puzzle domain

    Each state is represented by an instance of an eightPuzzle.
  """
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">,</span>puzzle<span style="font-weight: bold">):
    </span><span style="color: red">"Creates a new EightPuzzleSearchProblem which stores search information."
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>puzzle <span style="font-weight: bold">= </span>puzzle

  <span style="color: blue; font-weight: bold">def </span>getStartState<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span>puzzle
      
  <span style="color: blue; font-weight: bold">def </span>isGoalState<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">,</span>state<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span>state<span style="font-weight: bold">.</span>isGoal<span style="font-weight: bold">()
   
  </span><span style="color: blue; font-weight: bold">def </span>getSuccessors<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">,</span>state<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
      Returns list of (successor, action, stepCost) pairs where
      each succesor is either left, right, up, or down
      from the original state and the cost is 1.0 for each
    """
    </span>succ <span style="font-weight: bold">= []
    </span><span style="color: blue; font-weight: bold">for </span>a <span style="color: blue; font-weight: bold">in </span>state<span style="font-weight: bold">.</span>legalMoves<span style="font-weight: bold">():
      </span>succ<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>state<span style="font-weight: bold">.</span>result<span style="font-weight: bold">(</span>a<span style="font-weight: bold">), </span>a<span style="font-weight: bold">, </span><span style="color: red">1</span><span style="font-weight: bold">))
    </span><span style="color: blue; font-weight: bold">return </span>succ

  <span style="color: blue; font-weight: bold">def </span>getCostOfActions<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>actions<span style="font-weight: bold">):
     </span><span style="color: darkred">"""
      actions: A list of actions to take
 
     This method returns the total cost of a particular sequence of actions.  The sequence must
     be composed of legal moves
     """
     </span><span style="color: blue; font-weight: bold">return </span>len<span style="font-weight: bold">(</span>actions<span style="font-weight: bold">)

</span>EIGHT_PUZZLE_DATA <span style="font-weight: bold">= [[</span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">2</span><span style="font-weight: bold">, </span><span style="color: red">3</span><span style="font-weight: bold">, </span><span style="color: red">4</span><span style="font-weight: bold">, </span><span style="color: red">5</span><span style="font-weight: bold">, </span><span style="color: red">6</span><span style="font-weight: bold">, </span><span style="color: red">7</span><span style="font-weight: bold">, </span><span style="color: red">8</span><span style="font-weight: bold">], 
                     [</span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">7</span><span style="font-weight: bold">, </span><span style="color: red">8</span><span style="font-weight: bold">, </span><span style="color: red">2</span><span style="font-weight: bold">, </span><span style="color: red">3</span><span style="font-weight: bold">, </span><span style="color: red">4</span><span style="font-weight: bold">, </span><span style="color: red">5</span><span style="font-weight: bold">, </span><span style="color: red">6</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">], 
                     [</span><span style="color: red">4</span><span style="font-weight: bold">, </span><span style="color: red">3</span><span style="font-weight: bold">, </span><span style="color: red">2</span><span style="font-weight: bold">, </span><span style="color: red">7</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">5</span><span style="font-weight: bold">, </span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">6</span><span style="font-weight: bold">, </span><span style="color: red">8</span><span style="font-weight: bold">], 
                     [</span><span style="color: red">5</span><span style="font-weight: bold">, </span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">3</span><span style="font-weight: bold">, </span><span style="color: red">4</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">2</span><span style="font-weight: bold">, </span><span style="color: red">6</span><span style="font-weight: bold">, </span><span style="color: red">7</span><span style="font-weight: bold">, </span><span style="color: red">8</span><span style="font-weight: bold">], 
                     [</span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">2</span><span style="font-weight: bold">, </span><span style="color: red">5</span><span style="font-weight: bold">, </span><span style="color: red">7</span><span style="font-weight: bold">, </span><span style="color: red">6</span><span style="font-weight: bold">, </span><span style="color: red">8</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">4</span><span style="font-weight: bold">, </span><span style="color: red">3</span><span style="font-weight: bold">], 
                     [</span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">3</span><span style="font-weight: bold">, </span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">6</span><span style="font-weight: bold">, </span><span style="color: red">8</span><span style="font-weight: bold">, </span><span style="color: red">2</span><span style="font-weight: bold">, </span><span style="color: red">7</span><span style="font-weight: bold">, </span><span style="color: red">5</span><span style="font-weight: bold">, </span><span style="color: red">4</span><span style="font-weight: bold">]]

</span><span style="color: blue; font-weight: bold">def </span>loadEightPuzzle<span style="font-weight: bold">(</span>puzzleNumber<span style="font-weight: bold">):
  </span><span style="color: darkred">"""
    puzzleNumber: The number of the eight puzzle to load.
    
    Returns an eight puzzle object generated from one of the
    provided puzzles in EIGHT_PUZZLE_DATA.
    
    puzzleNumber can range from 0 to 5.
    
    &gt;&gt;&gt; print loadEightPuzzle(0)
    -------------
    | 1 |   | 2 |
    -------------
    | 3 | 4 | 5 |
    -------------
    | 6 | 7 | 8 |
    -------------
  """
  </span><span style="color: blue; font-weight: bold">return </span>EightPuzzleState<span style="font-weight: bold">(</span>EIGHT_PUZZLE_DATA<span style="font-weight: bold">[</span>puzzleNumber<span style="font-weight: bold">])

</span><span style="color: blue; font-weight: bold">def </span>createRandomEightPuzzle<span style="font-weight: bold">(</span>moves<span style="font-weight: bold">=</span><span style="color: red">100</span><span style="font-weight: bold">):
 </span><span style="color: darkred">"""
   moves: number of random moves to apply

   Creates a random eight puzzle by applying
   a series of 'moves' random moves to a solved
   puzzle.
 """
 </span>puzzle <span style="font-weight: bold">= </span>EightPuzzleState<span style="font-weight: bold">([</span><span style="color: red">0</span><span style="font-weight: bold">,</span><span style="color: red">1</span><span style="font-weight: bold">,</span><span style="color: red">2</span><span style="font-weight: bold">,</span><span style="color: red">3</span><span style="font-weight: bold">,</span><span style="color: red">4</span><span style="font-weight: bold">,</span><span style="color: red">5</span><span style="font-weight: bold">,</span><span style="color: red">6</span><span style="font-weight: bold">,</span><span style="color: red">7</span><span style="font-weight: bold">,</span><span style="color: red">8</span><span style="font-weight: bold">])
 </span><span style="color: blue; font-weight: bold">for </span>i <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>moves<span style="font-weight: bold">):
   </span><span style="color: green; font-style: italic"># Execute a random legal move
   </span>puzzle <span style="font-weight: bold">= </span>puzzle<span style="font-weight: bold">.</span>result<span style="font-weight: bold">(</span>random<span style="font-weight: bold">.</span>sample<span style="font-weight: bold">(</span>puzzle<span style="font-weight: bold">.</span>legalMoves<span style="font-weight: bold">(), </span><span style="color: red">1</span><span style="font-weight: bold">)[</span><span style="color: red">0</span><span style="font-weight: bold">])
 </span><span style="color: blue; font-weight: bold">return </span>puzzle

<span style="color: blue; font-weight: bold">if </span>__name__ <span style="font-weight: bold">== </span><span style="color: red">'__main__'</span><span style="font-weight: bold">:
  </span>puzzle <span style="font-weight: bold">= </span>createRandomEightPuzzle<span style="font-weight: bold">(</span><span style="color: red">25</span><span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">print</span><span style="font-weight: bold">(</span><span style="color: red">'A random puzzle:'</span><span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">print</span><span style="font-weight: bold">(</span>puzzle<span style="font-weight: bold">)
  
  </span>problem <span style="font-weight: bold">= </span>EightPuzzleSearchProblem<span style="font-weight: bold">(</span>puzzle<span style="font-weight: bold">)
  </span>path <span style="font-weight: bold">= </span>search<span style="font-weight: bold">.</span>breadthFirstSearch<span style="font-weight: bold">(</span>problem<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">print</span><span style="font-weight: bold">(</span><span style="color: red">'BFS found a path of %d moves: %s' </span><span style="font-weight: bold">% (</span>len<span style="font-weight: bold">(</span>path<span style="font-weight: bold">), </span>str<span style="font-weight: bold">(</span>path<span style="font-weight: bold">)))
  </span>curr <span style="font-weight: bold">= </span>puzzle
  i <span style="font-weight: bold">= </span><span style="color: red">1
  </span><span style="color: blue; font-weight: bold">for </span>a <span style="color: blue; font-weight: bold">in </span>path<span style="font-weight: bold">:
    </span>curr <span style="font-weight: bold">= </span>curr<span style="font-weight: bold">.</span>result<span style="font-weight: bold">(</span>a<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">print</span><span style="font-weight: bold">(</span><span style="color: red">'After %d move%s: %s' </span><span style="font-weight: bold">% (</span>i<span style="font-weight: bold">, (</span><span style="color: red">""</span><span style="font-weight: bold">, </span><span style="color: red">"s"</span><span style="font-weight: bold">)[</span>i<span style="font-weight: bold">&gt;</span><span style="color: red">1</span><span style="font-weight: bold">], </span>a<span style="font-weight: bold">))
    </span><span style="color: blue; font-weight: bold">print</span><span style="font-weight: bold">(</span>curr<span style="font-weight: bold">)
    
    </span>raw_input<span style="font-weight: bold">(</span><span style="color: red">"Press return for the next state..."</span><span style="font-weight: bold">)   </span><span style="color: green; font-style: italic"># wait for key stroke
    </span>i <span style="font-weight: bold">+= </span><span style="color: red">1
</span>
  </pre>
  </body>
  </html>
  